package com.xy6.algo.sort;

import java.util.Arrays;

/**
 * 桶排序
 * <pre>
 * 时间复杂度：O(n+c)（C=N*(logN-logM)），空间复杂度：O(n+m)
 * 
 * 将n个元素（元素长度相同）放到m个桶中，桶已按照从小到大排序
 * 遍历n个元素，取第一个元素，根据映射函数（如函数f(x)=x）计算其对应的桶编号i，将元素放到桶i中
 * 取第二个元素，根据映射函数计算其对应的桶编号j，将元素放到桶j中
 * 直到元素遍历完毕。
 * 遍历桶，取第一个桶，如果元素个数<=1，则无需处理。否则使用插入排序，对桶中的元素进行排序，从小到大
 * 取第二个桶，如果元素个数<=1，则无需处理。否则使用插入排序，对桶中的元素进行排序，从小到大
 * 直到桶遍历完毕。
 * 遍历桶中所有元素，空桶跳过，得到有序的元素集合。
 * 
 * 稳定排序
 * 以空间换时间
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-01
 */
public class SortBucket {

	public static void main(String[] args) {
		test2();
	}
	
	public static void test2(){
		int[] arr = { 99, 65, 24, 47, 50, 88, 33, 66, 67, 31, 18 };
		// 桶个数
		int bucketSize = 100;
		
		int[] arr2 = sort(arr, bucketSize, 100);
		System.out.println(Arrays.toString(arr2));
	}
	
	/**
	 * 桶排序
	 * 
	 * @param arr
	 * @param bucketSize
	 * @param maxElem
	 * @return
	 */
	public static int[] sort(int[] arr, int bucketSize, int maxElem){
		// 单桶中元素个数
		int elemSize = maxElem / bucketSize;
		int[][] buckets = new int[bucketSize][];
		for (int i = 0; i < arr.length; i++) {
			int bucketIdx = getBucketIdx(arr[i], elemSize);
			save(arr[i], bucketIdx, buckets);
		}
		
		// 桶中元素排序
		sort(buckets);
		
		// 输出桶中的元素
		int[] arr2 = new int[arr.length];
		int count = 0;
		for (int i = 0; i < bucketSize; i++) {
			int[] bucket = buckets[i];
			if (null == bucket || bucket.length == 0) {
				continue;
			}
			for (int j = 0; j < bucket.length; j++) {
				arr2[count++] = bucket[j];
			}
		}
		return arr2;
	}
	
	/**
	 * 映射函数
	 * 
	 * <p>将1-100映射到20个桶中
	 * 
	 * @param i
	 */
	private static int getBucketIdx(int i, int bucketSize){
		return i/bucketSize;
	}
	
	/**
	 * 将值保存到一个桶中
	 * 
	 * @param val
	 * @param bucketIdx
	 * @param buckets
	 */
	private static void save(int val, int bucketIdx, int[][] buckets){
		if(null == buckets[bucketIdx]){
			buckets[bucketIdx] = new int[1];
			buckets[bucketIdx][0] = val;
			return;
		}
		int len = buckets[bucketIdx].length; 
		buckets[bucketIdx] = copy(buckets[bucketIdx], len + 1);
		buckets[bucketIdx][len] = val;
	}
	
	/**
	 * 将一个数组拷贝到一个长度为len的新数组中
	 * 
	 * @param arr
	 * @param len
	 * @return
	 */
	private static int[] copy(int[] arr, int len){
		int[] arr2 = new int[arr.length + 1];
		for(int i=0; i<arr.length; i++){
			arr2[i] = arr[i];
		}
		return arr2;
	}
	
	/**
	 * 对每个子数组进行排序
	 * 
	 * @param bucket
	 */
	private static void sort(int[][] arr){
		for (int i = 0; i < arr.length; i++) {
			if(null == arr[i] || arr[i].length <= 1){
				continue;
			}
			SortInsert.sort(arr[i]);
		}
	}

}
